package Sort;

/**
 * @author shy_black
 * @date 2019/3/10 20:39
 * @Description:归并排序
 * 应用分治思想，如何在O(n)内寻找一个无序数组的第k大元素？
 * 分治思想：将一个大的问题分为若干个足够小的问题求解
 * 当所有小问题解决后，将结果合并起来就是整个问题的求解
 *
 */
public class 归并排序 {
    public static void main(String[] args) {
        int[] arr = new int[]{11,8,3,9,7,1,2,5};
        mergeSort(arr);
        for(int i: arr) {
            System.out.print(i+"_");
        }
    }
    public static void mergeSort(int[] arr) {
        int n = arr.length;
        if(n <= 1)
            return;
        int mid = n / 2;
        mergeInternal(arr,0,n-1);
    }
    //将数组名，左边元素，右边元素传入，方便再次分割
    private static void mergeInternal(int[] arr,int low,int high) {
        if(low >= high)
            return;
        int mid = (low+high)/2;
        //左边数组
        mergeInternal(arr,low,mid);
        //右边数组
        mergeInternal(arr,mid+1,high);
        //合并，把low->mid，mid+1->high俩个小数组合并
        merge(arr,low,mid,high);
    }
    //俩个有序数组合并为一个有序数组
    private static void merge(int[] arr,int p,int q,int r) {
        int i = p;
        int j = q + 1;
        int[] temp = new int[r-p+1];
        int k = 0;
        //此时俩个数组中均有元素
        while(i <=q && j <= r) {
            if(arr[i] < arr[j]) {
                //第一个数组中的相同位置元素最小
                temp[k++] = arr[i++];
            }else {
                temp[k++] = arr[j++];
            }
        }
        //判断哪个元素还没有走完
        int start = i;
        int end = q;
        if(j <= r) {
            start = j;
            end = r;
        }
        //把剩下元素都放在temp后中即可
        while(start <= end ) {
            temp[k++] = arr[start++];
        }
        //将临时空间中的已经合并好的元素拷贝回原数组
        for(i = 0;i < r-p+1;i++) {
            arr[p+i] = temp[i];
        }
    }

}
